package me.algo.tree;

import org.checkerframework.checker.units.qual.A;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;

/**
 * @author guozheng
 * @date 2024/4/18
 */
public class T5 {
    public static void main(String[] args) {

    }

    /**
     * 113. 路径总和 II
     * @param root
     * @param targetSum
     * @return
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (Objects.isNull(root)) {
            return new ArrayList<>();
        }
        LinkedList<Pair> queue = new LinkedList<>();
        queue.add(new Pair(root, new LinkedList<>()));

        List<List<Integer>> rtn = new ArrayList<>();

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                size--;
                Pair pair = queue.removeFirst();
                TreeNode node = pair.node;
                if (node.left == null && node.right == null) {
                    int sum = pair.getSum();
                    int val = node.val;
                    if (sum + val == targetSum) {
                        List<Integer> nums = pair.nums;
                        LinkedList<Integer> target = new LinkedList<>(nums);
                        target.addLast(val);
                        rtn.add(target);
                    }
                    continue;
                }
                if (node.left != null) {
                    int val = node.val;
                    List<Integer> nums = pair.nums;
                    LinkedList<Integer> next = new LinkedList<>(nums);
                    next.addLast(val);
                    queue.addLast(new Pair(node.left, next));
                }
                if (node.right != null) {
                    int val = node.val;
                    List<Integer> nums = pair.nums;
                    LinkedList<Integer> next = new LinkedList<>(nums);
                    next.addLast(val);
                    queue.addLast(new Pair(node.right, next));
                }
            }
        }
        return rtn;
    }


    static record Pair(TreeNode node, List<Integer> nums, int sum) {

        public Pair(TreeNode node, List<Integer> nums,int sum) {
            this.node = node;
            this.nums = nums;
            this.sum = sum;
        }

        public Pair(TreeNode node, List<Integer> nums) {
            this(node, nums, sum(nums));
        }

        private static int sum(List<Integer> list) {
            if (Objects.isNull(list)) {
                return 0;
            }
            return list.stream().reduce(0, Integer::sum);
        }


        public int getSum() {
            return sum;
        }
    }
}
